#include <iostream>
using namespace std;
#define maxn 51
#define maxm 10001
#define maxbz 32
const int INF = 1<<28;

int n,m;
bool G[maxn][maxn][maxbz];
int dis[maxn][maxn];

void init(){
    for(int k=1;k<=maxbz;k++){
        for(int i=1;i<=n;i++){
            for(int t=1;t<=n;t++){
                for(int j=1;j<=n;j++){
                    if(G[i][t][k-1] && G[t][j][k-1]){
                        G[i][j][k]=true;
                        dis[i][j]=1;
                    }
                }
            }
        }
    }
}

void floyd(){
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
        	for(int j=1;j<=n;j++)
                if(dis[i][j] > dis[i][k]+dis[k][j])
                    dis[i][j] = dis[i][k]+dis[k][j];
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dis[i][j]=INF;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        G[u][v][0]=true;
        dis[u][v]=1;
    }
    
    init();
    floyd();

    cout<<dis[1][n]<<endl;
    return 0;
}